class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    int nums[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int sum;
    void dfs(int k, int n, int pos)
    {
        // 当个数达到k个 && 路径和等于n时 收获结果集
        if(sum == n && path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        // 每个数字最多使用一次 
        for(int i = pos; i < 9; i++)
        {
            path.push_back(nums[i]);
            sum += nums[i];

            dfs(k, n, i + 1);

            // 恢复现场
            path.pop_back();
            sum -= nums[i];
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 0);
        return ret;
    }
};